package leetcode.Hot100;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author Cheng Jun
 * Description: 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
 * <p>
 * rows == matrix.length
 * cols == matrix[0].length
 * 1 <= row, cols <= 200
 * matrix[i][j] 为 '0' 或 '1'
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/maximal-rectangle
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @version 1.0 [['1','0','1','0','0'],['1','0','1','1','1'],['1','1','1','1','1'],['1','0','0','1','0']]
 * @date 2021/12/20 23:07
 * 字节面试题
 */
public class maximalRectangle {
    public static void main(String[] args) {
        maximalRectangle1(new char[][]{
                new char[]{'1', '1', '1'},
                new char[]{'0', '1', '1'},
                new char[]{'0', '1', '1'},
        });
    }

    // 1,1,1,0
    // 0,1,1,0
    // 0,1,1,0
    // 思路：对于复杂问题，一般需要由简入繁，二维矩阵求面积，那么如果是一维矩阵就是求线段长度，我们先将问题降维 到一维思考
    // 有一个 只包含 0，1 的数组，求连续 1 的长度，从头遍历，
    // 当前位置为0，那么当前为的长度就是0，如果当前位置是1，那么前一个位置的长度 + 1, 就等于当前位置的长度。如下图
    // 1,2,3,0
    // 0,1,2,0
    // 0,1,2,0
    // 一维的连续长度问题解决了，那么我们就只需要对众多一维累加，累加的条件是保证是矩形。
    // 我们以 每个非0位置作为 矩形的右下角，往上查找，取同列的较小值乘以高度
    static public int maximalRectangle(char[][] matrix) {
        int maxArea = 0;
        int m = matrix.length;
        if (m == 0) {
            return 0;
        }
        int n = matrix[0].length;
        int[][] left = new int[m][n];
        // 每一行
        for (int i = 0; i < m; i++) {
            // 行中的列
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    // 长度累积，每行开头没有left[i][j - 1]，需要判断一下j的情况
                    left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 大于 0 才有成为矩形的可能
                if (left[i][j] > 0) {
                    // 贪心：宽度定义
                    int width = left[i][j];
                    int height = 1;
                    maxArea = Math.max(maxArea, width * 1);
                    for (int k = i - 1; k >= 0; k--) {
                        // 往上查找的时候，需要重新选择较小边作为 width
                        width = Math.min(width, left[k][j]);
                        maxArea = Math.max(maxArea, width * (++height));
                    }
                }
            }
        }
        return maxArea;
    }

    static public int maximalRectangle1(char[][] matrix) {
        int m = matrix.length;
        if (m == 0) {
            return 0;
        }
        int n = matrix[0].length;
        int[][] left = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
                }
            }
        }

        int ret = 0;
        for (int j = 0; j < n; j++) { // 对于每一列，使用基于柱状图的方法
            int[] up = new int[m];
            int[] down = new int[m];

            Deque<Integer> stack = new LinkedList<Integer>();
            for (int i = 0; i < m; i++) {
                while (!stack.isEmpty() && left[stack.peek()][j] >= left[i][j]) {
                    stack.pop();
                }
                up[i] = stack.isEmpty() ? -1 : stack.peek();
                stack.push(i);
            }
            stack.clear();
            for (int i = m - 1; i >= 0; i--) {
                while (!stack.isEmpty() && left[stack.peek()][j] >= left[i][j]) {
                    stack.pop();
                }
                down[i] = stack.isEmpty() ? m : stack.peek();
                stack.push(i);
            }

            for (int i = 0; i < m; i++) {
                int height = down[i] - up[i] - 1;
                int area = height * left[i][j];
                ret = Math.max(ret, area);
            }
        }
        return ret;
    }

}
